数据结构--线性表
Table of Contents
数据结构
数据的逻辑结构
数据的逻辑结构分为 线性结构 和 非线性结构.
线性结构有: 数组, 栈, 队列, 串, 等等.
非线性结构有: 树, 图, 等等.
数据的存储结构
存储结构也称为物理结构, 指数据结构在计算机中的表示.
- 顺序存储: 逻辑上相邻的元素在物理位置上也相邻. 优点是可以随机存储, 缺点是物理位置必须相邻, 可能会产生外部碎片.
- 链接存储: 借助指针表示元素之间的逻辑关系, 不要求逻辑上相邻的元素在物理位置上也相邻. 优点是不会出现碎片, 缺点是指针需要额外占用空间, 并且只能顺序存储.
- 索引存储: 在存储元素的信息的同时, 额外建立了索引表, 索引表中的每一项称为索引项, 索引项的一般形式是: (关键字, 地址). 优点是检索速度快, 缺点是索引表需要额外占用空间, 并且在增加或删除数据时需要修改索引表, 会花费较多的时间.
- 散列存储: 直接根据元素的关键字计算元素的存储地址. 优点是检索, 增加或删除速度都很快, 缺点是散列函数如果不好, 可能会在存储时出现冲突, 需要额外处理冲突.
线性表
线性表的特点:
- 个数有限.
- 线性表中的元素在逻辑上有顺序性.
- 线性表中的元素类型都相同.
顺序表
线性表的顺序存储, 就称为顺序表.
顺序表中, 逻辑上相邻的元素, 物理位置上也相邻.
特点: 可以随机访问, 通过首地址和元素序号, 可以在 \(O(1)\) 的时间内找到指定元素; 存储密度高, 每个结点只存储数据元素; 插入和删除需要移动大量元素.
复杂度
插入
最好情况: 表尾插入, \(O(1)\).
最坏情况: 表头插入, \(O(n)\).
平均情况: \(O(n)\).
删除
最好情况: 表尾删除, \(O(1)\).
最坏情况: 表头删除, \(O(n)\).
平均情况: \(O(n)\).
查找
最好情况: 表头元素, \(O(1)\).
最坏情况: 表尾元素, \(O(n)\).
平均情况: \(O(n)\).
链表
链表不要求逻辑上相邻的两个元素在物理位置上也相邻, 它们通过"链"建立起数据元素之间的逻辑关系, 因此, 链表的插入删除不需要移动元素, 只需要改变指针的指向即可.
单链表
对于单链表中的每个结点, 除了要存放元素自身的信息之外, 还要存储一个指向其后继的指针.
利用单链表, 可以解决顺序表需要大量连续存储空间的缺点, 但是单链表附加指针域, 也带来了浪费存储空间的缺点. 单链表的存取不是随机的, 需要从表头开始遍历.
头指针 用来指向一个单链表.
头结点 是单链表中第一个结点前面附加的一个额外的结点, 仅为了操作方便, 可以在头结点的数据域存放表长, 头结点的指针域指向单链表的第一个结点.
头结点并非一定要有, 但如果使用了头结点, 有以下两个好处:
- 单链表第一个结点的位置存放在头结点中, 可以让单链表第一个结点的操作和后面的结点操作一致, 无需特殊物理.
- 如果没有头结点, 链表为空时, 头指针为 NULL. 有头结点之后, 头指针指向头结点, 所以头指针不会为 NULL, 这统一了空表和非空表的处理.
建立单链表
单链表的建立有头插法和尾插法两种办法.
头插法每次在头结点之后插入元素, 所以结点的次序和输入数据的顺序不一致.
尾插法需要增加一个尾指针, 每次在表尾插入元素. 实现比头插法稍微复杂一点点.
设单链表的长度为 \(n\), 两种算法的时间复杂度都是 \(O(n)\), 每个结点的插入时间为 \(O(1)\).
查找
查找操作需要遍历单链表, 时间复杂度为 \(O(n)\).
插入
原本链表中两个元素的关系为: a->b, 要插入结点 x, 使得关系变成: a->x->b
指针p 指向 结点a, 指针s 指向 结点x.
操作顺序为:
s->next = p->next; p->next = s;
顺序不可颠倒, 否则链表会断开.
如果要在 结点a 前面插入新结点, 也可以和上面一样操作, 然后做个交换即可.
时间复杂度 \(O(1)\).
删除
假设结点的关系为: a->b->c, 要删除 结点b.
指针p 指向 结点a.
q = p->next; // 令 q 指向被删除结点 p->next = q->next; free(q);
时间复杂度为 \(O(n)\).
双链表
单链表的缺点: 每个结点只有一个指向后继的指针, 如果要访问某个结点的前驱, 需要重新遍历.
双链表的意思就是, 为每个结点配置两个指针, 一个指向前驱(prior), 一个指向后继(next).
双链表的操作与单链表大致相同, 但在插入和删除时, 需要对 prior 指针也做出修改.
插入
在结点 *p 后面插入结点 *s:
s->next = p->next; p->next-> prior = s; s->prior = p; p->next = s;
删除
删除结点 *p 的后继结点 *q:
p->next = q->next; q->next->prior = p; free(q);
循环链表
循环单链表
循环单链表与单链表的区别: 表中最后一个结点的指针不是 NULL, 而是指向头结点, 从而整个链表形成一个环.
判断循环单链表是否为空: 头结点的指针是否等于头结点, 在单链表中, 是判断头结点的指针是否为空.
由于循环单链表是一个环, 所以在任何一个位置进行插入和删除, 都是一样的, 无须特殊对待.
如果对循环单链表常做的操作是在表头和表尾进行的, 则可以只设置尾指针, 而不需要头指针. 因为如果保留的是头指针, 在表尾进行操作需要遍历到表尾, 而如果保留的是尾指针, 只需要 r->next 就可以得到头指针.
循环双链表
循环双链表就是每个结点都有前驱和后继指针, 头结点的 prior 指针指向表尾结点.
Generated by Emacs 25.x(Org mode 8.x)
Copyright © 2014 - Pinvon - Powered by EGO
